package offer.zixing.chapter03;

/**
 * 不含重复字符的最长子字符串
 *
 * 输入一个字符串，求该字符串中不含重复字符的最长连续子字符串的长度。
 * 例如，输入字符串"babcca"，它最长的不含重复字符串的子字符串是"abc"，长度为3。
 */
public class Test016 {
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring1("babcca"));
    }

    public static int lengthOfLongestSubstring1(String s) {
        int[] counts = new int[256];
        int longest = s.length() > 0 ? 1 : 0;
        for (int i = 0, j = -1; i < s.length(); i++) {
            counts[s.charAt(i)]++;
            while (hasGreaterThan1(counts)) {
                j++;
                counts[s.charAt(j)]--;
            }
            longest = Math.max(i - j, longest);
        }
        return longest;
    }

    private static boolean hasGreaterThan1(int[] counts) {
        for (int count : counts) {
            if (count > 1) {
                return true;
            }
        }
        return false;
    }

    public static int lengthOfLongestSubstring2(String s) {
        int[] counts = new int[256];
        int longest = s.length() > 0 ? 1 : 0;
        int countDup = 0;
        for (int i = 0, j = -1; i < s.length(); i++) {
            counts[s.charAt(i)]++;
            if (counts[s.charAt(i)] == 2) {
                countDup++;
            }
            while (countDup > 0) {
                j++;
                counts[s.charAt(j)]--;
                if (counts[s.charAt(j)] == 1) {
                    countDup--;
                }
            }
            longest = Math.max(i - j, longest);
        }
        return longest;
    }
}
